#!/usr/bin/env python3

class Solution:
    def is_valid_sudoku(self, board):
        # key -> [set(row), set(column), set(sub_box)]
        digits_maps = {}
        for row_index, rows in enumerate(board):
            for column_index, column in enumerate(rows):
                ch = rows[column_index]
                if ch == '.':
                    continue
                sub_box = int(row_index / 3) * 3 + int(column_index / 3)
                if ch in digits_maps:
                    row_set, column_set, sub_box_set = digits_maps[ch]
                    if row_index in row_set:
                        return False
                    else:
                        row_set.add(row_index)
                    if column_index in column_set:
                        return False
                    else:
                        column_set.add(column_index)
                    if sub_box in sub_box_set:
                        return False
                    else:
                        sub_box_set.add(sub_box)
                else:
                    record = [{row_index}, {column_index}, {sub_box}]
                    digits_maps[ch] = record
        return True


if __name__ == '__main__':
#    input = [
#        ["5","3",".",".","7",".",".",".","."],
#        ["6",".",".","1","9","5",".",".","."],
#        [".","9","8",".",".",".",".","6","."],
#        ["8",".",".",".","6",".",".",".","3"],
#        ["4",".",".","8",".","3",".",".","1"],
#        ["7",".",".",".","2",".",".",".","6"],
#        [".","6",".",".",".",".","2","8","."],
#        [".",".",".","4","1","9",".",".","5"],
#        [".",".",".",".","8",".",".","7","9"]]
#    input = [
#        ["8","3",".",".","7",".",".",".","."],
#        ["6",".",".","1","9","5",".",".","."],
#        [".","9","8",".",".",".",".","6","."],
#        ["8",".",".",".","6",".",".",".","3"],
#        ["4",".",".","8",".","3",".",".","1"],
#        ["7",".",".",".","2",".",".",".","6"],
#        [".","6",".",".",".",".","2","8","."],
#        [".",".",".","4","1","9",".",".","5"],
#        [".",".",".",".","8",".",".","7","9"]]
    input = [[".",".","4",".",".",".","6","3","."],
             [".",".",".",".",".",".",".",".","."],
             ["5",".",".",".",".",".",".","9","."],
             [".",".",".","5","6",".",".",".","."],
             ["4",".","3",".",".",".",".",".","1"],
             [".",".",".","7",".",".",".",".","."],
             [".",".",".","5",".",".",".",".","."],
             [".",".",".",".",".",".",".",".","."],
             [".",".",".",".",".",".",".",".","."]]
    solution = Solution()
    assert not solution.is_valid_sudoku(input)
